package com.example.zzy.zzytest.data.structure.list.joseph;


/**
 * Joseph问题：
 * n个人围坐，k(k<=n)位置的人从1开始报数，报到m为止，该人出列，然后下一个人从1开始在报到m出列
 * 以此类推到所有人出列为止，求出列的顺序
 * <p>
 * 单向环形链表
 * 理解:单向代表着删除时需要记录前驱节点，在最开始的时候，同时记录着first和tail
 * 环形代表着没有一个普遍意义的head，first只是记录当前数数的第一个节点，数完删完都要后移
 */
public class Joseph {
    public static void main(String[] args) {
        SingleCircleLinkedList list = new SingleCircleLinkedList();
        list.addChilds(5);
        list.show();
        list.josephDequeue(5, 1, 2);
    }
}

class SingleCircleLinkedList {
    private Child first = null;


    //创建一个有nums个人的环形链表
    public void addChilds(int nums) {
        if (nums < 0) {
            System.out.println("初始队列长度输入值为负，不合规");
        }

        //有一个节点指向最后的节点
        Child cur = null;
        for (int i = 1; i <= nums; i++) {
            Child temp = new Child(i);

            if (i == 1) {
                first = temp;
                first.setNext(first);
                cur = first;
            } else {
                cur.setNext(temp);
                cur = temp;
                cur.setNext(first);
            }
        }
    }

    public void show() {
        Child cur = first;
        while (true) {
            System.out.println(cur.getNo());
            if (cur.getNext() == first) {
                break;
            }
            cur = cur.getNext();
        }
    }

    /**
     * joseph问题求出队顺序
     *
     * @param n n人队列
     * @param k 从1开始数，到第k个开始报数
     * @param m 报数的人从1开始报，到第m个出队
     *          n5 k1 m2
     *          <p>
     *          1 2 3 4 5
     */
    public void josephDequeue(int n, int k, int m) {
        if (first == null || k < 1 || k > n) {
            System.out.println("前提条件检查不通过");
        }

        //1.找到最后一个节点
        Child cur = first;
        while (true) {
            if (cur.getNext() == first) {
                break;
            }
            cur = cur.getNext();
        }

        //2.first和cur都向前走k-1,因为从1开始数
        for (int i = 0; i < k - 1; i++) {
            first = first.getNext();
            cur = cur.getNext();
        }

        while (true) {
            if (cur == first) {
                System.out.println("最后剩余了" + first.getNo());
                break;
            }

            //3.first和cur都向前走m-1,因为从1开始数
            for (int i = 0; i < m - 1; i++) {
                first = first.getNext();
                cur = cur.getNext();
            }

            //4.first指向的节点删除
            System.out.println("本次删除了" + first.getNo());
            first = first.getNext();
            cur.setNext(first);
        }

    }
}

class Child {
    private int no;
    private Child next;

    public Child(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Child getNext() {
        return next;
    }

    public void setNext(Child next) {
        this.next = next;
    }
}